package cn.zifangsky.graph;

import cn.zifangsky.queue.LinkQueue;
import cn.zifangsky.queue.Queue;

import java.text.MessageFormat;
import java.util.Arrays;
import java.util.List;
import java.util.function.BiConsumer;
import java.util.function.Consumer;

/**
 * 邻接矩阵
 *
 * @author zifangsky
 * @date 2019/1/18
 * @since 1.0.0
 */
public class GraphMatrix {
    /**
     * 顶点个数
     */
    private int vertexNum;

    /**
     * 顶点数组
     */
    private List<String> vertexList;

    /**
     * 邻接矩阵
     */
    private int[][] matrix;

    /**
     * 是否是有向图（默认为无向图）
     */
    private boolean directedGraph = false;

    public int getVertexNum() {
        return vertexNum;
    }

    public List<String> getVertexList() {
        return vertexList;
    }

    public int[][] getMatrix() {
        return matrix;
    }

    public boolean isDirectedGraph() {
        return directedGraph;
    }

    /**
     * 构造方法
     * @author zifangsky
     * @date 2019/1/22 14:26
     * @since 1.0.0
     * @param vertexArray 顶点数组
     * @param weightList 顶点之间的权重
     */
    public GraphMatrix(String[] vertexArray, List<Edge> weightList) {
        if (vertexArray == null || vertexArray.length < 1
                || weightList == null) {
            throw new IllegalArgumentException("Illegal initial initialArray");
        }

        this.vertexNum = vertexArray.length;
        this.vertexList = Arrays.asList(vertexArray);

        //初始化图
        this.initGraph(weightList, this.directedGraph);
    }

    /**
     * 构造方法
     * @author zifangsky
     * @date 2019/1/22 14:26
     * @since 1.0.0
     * @param vertexArray 顶点数组
     * @param weightList 顶点之间的权重
     * @param directedGraph 是否是有向图（默认为无向图）
     */
    public GraphMatrix(String[] vertexArray, List<Edge> weightList, boolean directedGraph) {
        if (vertexArray == null || vertexArray.length < 1
                || weightList == null || weightList.size() < 1) {
            throw new IllegalArgumentException("Illegal initial initialArray");
        }

        this.vertexNum = vertexArray.length;
        this.vertexList = Arrays.asList(vertexArray);
        this.directedGraph = directedGraph;

        //初始化图
        this.initGraph(weightList, this.directedGraph);
    }

    /**
     * 初始化图
     * @param weightList 顶点之间的权重
     * @param directedGraph 是否是有向图（默认为无向图）
     */
    private void initGraph(List<Edge> weightList, boolean directedGraph){
        //1. 初始化矩阵
        matrix = new int[vertexNum][vertexNum];
        for(int i = 0; i < vertexNum; i++){
            for(int j = 0; j < vertexNum; j++){
                if(i == j){
                    matrix[i][j] = 0;
                }else{
                    matrix[i][j] = -1;
                }
            }
        }

        //2. 根据边的权重重新设置矩阵
        for(Edge edge : weightList){
            //起始、结束索引
            int startIndex = vertexList.indexOf(edge.getStartVertex());
            int endIndex = vertexList.indexOf(edge.getEndVertex());

            if(startIndex < 0 || endIndex < 0){
                throw new RuntimeException(MessageFormat.format("初始化数据存在问题：{0}", edge));
            }

            //权重赋值
            matrix[startIndex][endIndex] = edge.getWeight() < -1 ? -1: edge.getWeight();

            //如果是无向图，相反的边也赋值
            if(!directedGraph){
                matrix[endIndex][startIndex] = edge.getWeight() < -1 ? -1: edge.getWeight();
            }
        }
    }

    /**
     * 遍历图中哪些顶点相连
     * @author zifangsky
     * @date 2019/1/22 15:20
     * @since 1.0.0
     * @param consumer consumer
     */
    public void foreach(BiConsumer<String, String> consumer){
        if(consumer != null){
            for(int i = 0; i < vertexNum; i++){
                for(int j = 0; j < vertexNum; j++){
                    //存在边
                    if(matrix[i][j] > 0){
                        consumer.accept(vertexList.get(i), vertexList.get(j));
                    }
                }
            }
        }
    }

    /**
     * DFS（深度优先搜索）
     * @author zifangsky
     * @date 2019/1/22 16:07
     * @since 1.0.0
     * @param consumer consumer
     */
    public void dfsForeach(Consumer<String> consumer){
        //标识每个顶点是否被访问
        boolean[] visited = new boolean[vertexNum];
        for(int i = 0; i < vertexNum; i++){
            visited[i] = false;
        }

        for(int i = 0; i < vertexNum; i++){
            if(!visited[i]){
                this.dfs(visited, i, consumer);
            }
        }
    }

    /**
     * DFS（深度优先搜索）
     * @param visited 标识每个顶点是否被访问
     * @param vertexIndex 顶点索引
     * @param consumer consumer
     */
    private void dfs(boolean[] visited, int vertexIndex, Consumer<String> consumer){
        //1. 输出当前顶点，并将标识置为——已访问
        consumer.accept(vertexList.get(vertexIndex));
        visited[vertexIndex] = true;

        //2. 遍历当前顶点的相邻节点
        for(int j = 0; j < vertexNum; j++){
            //存在边，并且相邻顶点没有被访问过
            if(matrix[vertexIndex][j] > 0 && !visited[j]){
                this.dfs(visited, j, consumer);
            }
        }
    }

    /**
     * BFS（宽度优先搜索）
     * @author zifangsky
     * @date 2019/1/22 16:18
     * @since 1.0.0
     * @param consumer consumer
     */
    public void bfsForeach(Consumer<String> consumer){
        //定义一个队列
        Queue<String> queue = new LinkQueue<>();

        //标识每个顶点是否被访问
        boolean[] visited = new boolean[vertexNum];
        for(int i = 0; i < vertexNum; i++){
            visited[i] = false;
        }

        queue.push(vertexList.get(0));

        //1. 如果队列不为空，则一直遍历
        while (!queue.isEmpty()){
            //2. 出队，获取顶点
            String vertex = queue.pop();
            int vertexIndex = vertexList.indexOf(vertex);
            consumer.accept(vertex);

            //3. 标识改顶点已经被访问
            visited[vertexIndex] = true;

            //4. 遍历当前顶点的相邻节点
            for(int j = 0; j < vertexNum; j++){
                //5. 存在边，并且相邻顶点没有被访问过，则将之加入到队列中
                if(matrix[vertexIndex][j] > 0 && !visited[j]){
                    queue.pushIfNotExist(vertexList.get(j));
                }
            }
        }
    }

}
